using System;
using System.Collections.Generic;
using System.Text;

namespace DeflateLib
{    
    /// <summary>
    /// Implemented recommended by DEFLATE specification compressor:
    /// the algorithm that find substrings. It's recommended by the
    /// RFC.
    /// 
    /// Has some optimizations to support LZ77CompressionSettings. Some
    /// of those settings may not work as it's implemented in the ZLIB.
    /// </summary>
    /// <see cref="LZ773ByteHash"/>
    class LZ77Compressor : ICompressor
    {
        const int MaxLength = 258;
        const int MaxDistance = 32768;
		
		LZ77Window window;
		LZ773ByteHash hash;
        LZ77CompressorSettings settings;
        int stoppedAt;

        internal LZ77CompressorSettings Settings
        {
            get { return settings; }
        }

        internal LZ77Compressor()
            : this(LZ77CompressorSettings.Default)
        {
        }

		internal LZ77Compressor(LZ77CompressorSettings settings)
		{
            this.settings = settings;
            this.window = new LZ77Window(MaxDistance * 2);
            this.hash = new LZ773ByteHash(MaxDistance);
            this.stoppedAt = 0;
		}

		public void Initialize(byte[] data, int index, int length)
		{
            if (window.Position + length > window.Size)
            {
                int shiftLength = window.Position - MaxDistance;
                window.Shift(shiftLength);
                if (stoppedAt >= shiftLength)
                {
                    stoppedAt -= shiftLength;
                }
                else
                {
                    hash.Skip(shiftLength - stoppedAt);
                    stoppedAt = 0;
                }
            }
            window.AppendData(data, index, length);
		}
		
		public CompressedData Compress(byte[] data, int index, int length)
		{
			if(window.Position + length > window.Size)
			{
				int shiftLength = window.Position - MaxDistance;
				window.Shift(shiftLength);
                if (stoppedAt >= shiftLength)
                {
                    stoppedAt -= shiftLength;
                }
                else
                {
                    hash.Skip(shiftLength - stoppedAt);
                    stoppedAt = 0;
                }                
			}
			
			int lastPosition = window.Position;
			window.AppendData(data, index, length);
            if (stoppedAt < lastPosition)
            {
                hash.Push(window.Data, stoppedAt, lastPosition - stoppedAt);
            }

            CompressedData compressedData;
            if (Settings.NiceLength > 0)
            {
                compressedData = Run(hash, window.Data, lastPosition, length, out stoppedAt);
            }
            else
            {
                compressedData = CopyNonDeflated(window.Data, lastPosition, length);
            }

			return compressedData;
		}

        public CompressedData CompressFinal()
        {
            return null;
        }

        private CompressedData CopyNonDeflated(byte[] data, int index, int length)
        {
            CompressedData compressedData = new CompressedData();
            compressedData.Codes.Capacity = length + 1;
            for (int i = 0; i < length; i++)
            {
                compressedData.WriteByte(data[i]);
            }
            return compressedData;
        }

        private CompressedData Run(LZ773ByteHash hash, byte[] data, int index, int length, out int stoppedAt)
		{
            CompressedData compressedData = new CompressedData();

            SubstringMatch? nextMatch = null;

            int i = 0;
			while (i < length - 2)
			{
				LZ773ByteHash.Iterator listIterator;
				listIterator = hash.Get(data, index + i);
				if (listIterator != null)
				{
                    SubstringMatch match;
                    if (nextMatch.HasValue)
                    {
                        match = nextMatch.Value;
                        nextMatch = null;
                    }
                    else
                    {
                        match = FindMatch(data, index, length, i, listIterator, 3);
                    }

					bool emitMatch = match.Length >= 3;
					if (emitMatch && i < length - 3 &&
                        match.Length < settings.MaxLazy)
					{
						// lazy matching
						LZ773ByteHash.Iterator nextListIterator;
						nextListIterator = hash.Get(data, index + i + 1);
						if (nextListIterator != null)
						{
                            SubstringMatch match2;
							match2 = FindMatch(data, index, length, i + 1, nextListIterator, match.Length + 1);

                            if (match2.Length > match.Length)
                            {
                                nextMatch = match2;
                                emitMatch = false;
                            }
						}
					}

					if (emitMatch)
					{
                        compressedData.WriteDistanceLength(i - match.Index, match.Length);
						hash.Push(data, index + i);
						i += match.Length;
						hash.Skip(match.Length - 1);
					}
					else
					{
                        compressedData.WriteByte(data[index + i]);
						hash.Push(data, index + i);
						++i;
					}
				}
				else
				{
                    compressedData.WriteByte(data[index + i]);
					hash.Push(data, index + i);
					++i;
				}
			}
            stoppedAt = index + i;
			while(i < length)
			{
                compressedData.WriteByte(data[index + i]);
				i++;
			}
            return compressedData;
		}

        struct SubstringMatch
        {
            public int Index;
            public int Length;
        }

		private SubstringMatch FindMatch(byte[] data, int index, int length, int i, 
			LZ773ByteHash.Iterator iterator, int minMatch)
		{
            int maxChainLength = settings.MaxChainLength;
            
            int maxMatch = 0;
			int maxMatchIndex = -1;
			int chainPosition = 0;
            int lastIndexToBeEqual = minMatch - 1;

			while(iterator.MoveNext())
			{
				int j = 0;
				int currentIndex = i - iterator.CurrentDistance;
                if (i + lastIndexToBeEqual >= length)
                    break; // iterator items are ordered. Stop when no larger string appear

                if (data[index + currentIndex + lastIndexToBeEqual] == data[index + i + lastIndexToBeEqual])
                {
                    // this string can be larger

                    while (j < MaxLength && i + j < length &&
                        data[index + currentIndex + j] == data[index + i + j])
                    {
                        ++j;
                    }
                    if (j >= maxMatch)
                    {
                        maxMatch = j;
                        lastIndexToBeEqual = j;
                        maxMatchIndex = currentIndex;
                        if (maxMatch >= settings.NiceLength)
                            break;
                    }

                    if (maxMatch >= settings.GoodLength)
                    {
                        maxChainLength >>= 2;
                    }
                }

				if (++chainPosition >= maxChainLength)
				{
					break;
				}
			}

            SubstringMatch match = new SubstringMatch();
            match.Length = maxMatch;
            match.Index = maxMatchIndex;
            return match;
        }

	}
}
